package com.celan.year2023.month01.day19;

import java.util.*;

public class Solution {
    /**
     * leetcode2299
     */
    public boolean strongPasswordCheckerII(String password) {
        //至少8个字符
        if (password.length() < 8) return false;
        //至少包含一个小写英文字母
        boolean low = false;
        //至少包含 一个大写英文字母
        boolean upper = false;
        //至少包含 一个数字
        boolean digit = false;
        //至少包含 一个特殊字符 !@#$%^&*()-+
        boolean symbol = false;
        //不包含2个连续相同的字符
        for (int i = 0; i < password.length(); i++) {
            char c = password.charAt(i);
            if (i != password.length() - 1 && c == password.charAt(i + 1)) return false;
            else if (c >= 'a' && c <= 'z') low = true;
            else if (c >= 'A' && c <= 'Z') upper = true;
            else if (c >= '0' && c <= '9') digit = true;
            else symbol = true;
        }
        return low && upper && digit && symbol;
    }

    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) return head;
        Set<Integer> set = new HashSet<Integer>();
        set.add(head.val);
        ListNode p = head;
        // 枚举前驱节点
        while (p.next != null) {
            // 当前待删除节点
            ListNode cur = p.next;
            if (set.add(cur.val)) {
                p = p.next;
            } else {
                p.next = p.next.next;
            }
        }
        return head;
    }

    public int kthToLast(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 1; i < k; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow.val;
    }

    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode headL = new ListNode(0);
        ListNode l = headL;
        ListNode headR = new ListNode(0);
        ListNode r = headR;
        ListNode p = head;
        while (p != null) {
            if (p.val < x) {
                l.next = p;
                l = l.next;
            } else {
                r.next = p;
                r = r.next;
            }
            p = p.next;
        }
        r.next = null;
        l.next = headR.next;
        return headL.next;
    }

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int n;
    int k;

    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        backTrack(1);
        return res;
    }

    private void backTrack(int idx) {
        //当一个路径元素到达k个，加入结果集
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            backTrack(i + 1);
            path.remove(path.size() - 1);
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        int res = 0;
        ListNode head = new ListNode(0);
        ListNode p = head;
        while (l1 != null && l2 != null) {
            int val = l1.val + l2.val + carry;
            if (val >= 10) {
                carry = 1;
                val -= 10;
            } else {
                carry = 0;
            }
            ListNode node = new ListNode(val);
            p.next = node;
            p = p.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while (l1 != null) {
            int val = l1.val + carry;
            if (val >= 10) {
                carry = 1;
                val -= 10;
            } else {
                carry = 0;
            }
            ListNode node = new ListNode(val);
            p.next = node;
            p = p.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            int val = l2.val + carry;
            if (val >= 10) {
                carry = 1;
                val -= 10;
            } else {
                carry = 0;
            }
            ListNode node = new ListNode(val);
            p.next = node;
            p = p.next;
            l2 = l2.next;
        }
        if (carry > 0) {
            ListNode node = new ListNode(carry);
            p.next = node;
        }
        return head.next;
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);
        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
